package com.cango.student.algorithm.sort;

/**
 * 快速排序
 * 时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
 * O(nlog2n) 	       O(n2)	      O(nlog2n)	    O(nlog2n)	不稳定	较复杂
 */
public class Quicksort4 {

    static int[] a = {40, 9, 20, 4, 30, 1, 54, 6, 8, 99};
    static int n;

    public static void quicksort(int left, int right) {
        if (left > right)
            return;

        int i = left;
        int j = right;
        int temp = a[left];

        while (i != j) {
            while (i < j && a[j] >= temp)
                j--;

            while (i < j && a[i] <= temp)
                i++;

            if (i < j) {
                int t = a[j];
                a[j] = a[i];
                a[i] = t;
            }
        }
        a[left] = a[i];
        a[i] = temp;
        // 继续处理左边的，这里是一个递归的过程
        quicksort(left, i - 1);
        // 继续处理右边的 ，这里是一个递归的过程
        quicksort(i + 1, right);

    }

    public static void main(String[] args) {
        n = 9;

        for (int i = 0; i <= n; i++)
            System.out.print(a[i] + " ");

        quicksort(0, n); //快速排序调用
        System.out.println("");
        //输出排序后的结果
        for (int i = 0; i <= n; i++)
            System.out.print(a[i] + " ");
    }
}
